//
//  main.cpp
//  树forXcode
//
//  Created by asus on 2020/7/6.
//  Copyright © 2020 唐沈飞. All rights reserved.
//

#include <iostream>
using namespace std;

typedef char DataType;  //便于后续修改数据类型

//二叉树的结点定义
typedef struct BTNode
{
    DataType data;  //默认data域为char，可修改
    struct BTNode *lchild;  //左孩子
    struct BTNode *rchild;  //右孩子
}BTNode,*PBTNode;

void CreateBiTree(PBTNode &T)
{
    DataType c;
    cin >> c;
    if( ' ' == c)
        T = NULL;
    else
    {
        T = (PBTNode)malloc(sizeof(BTNode));
        T->data = c;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void Visit(PBTNode p)
{
    //cout << "comming soon!" << endl;
    cout << p->data << " "; //读取结点数据
}

//先序遍历
void preorder(PBTNode p)
{
    if(p != NULL)
    {
        Visit(p);               //先遍历根结点
        preorder(p->lchild);    //再先序遍历左子树
        preorder(p->rchild);    //再先序遍历右子树
    }
}

//中序遍历
void inorder(PBTNode p)
{
    if(p != NULL)
    {
        inorder(p->lchild);     //先中序遍历左子树
        Visit(p);               //再遍历根结点
        inorder(p->rchild);     //再中序遍历右子树
    }
}

//后序遍历
void postorder(PBTNode p)
{
    if(p != NULL)
    {
        postorder(p->lchild);   //先后序遍历左子树
        postorder(p->rchild);   //再后序遍历右子树
        Visit(p);               //再遍历根结点
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    PBTNode p = NULL;
    CreateBiTree(p);
    preorder(p);
    cout << "Hello, World!\n";
    return 0;
}
